1. Field of the Invention
The present invention relates to an ACS (add-compare-select) device used, for example, in a Viterbi decoder that performs maximum-likelihood decoding of a convolutionally encoded data sequence.
2. Background of the Invention
Usually, in a Viterbi decoder, a convolutionally encoded data sequence is input, and for each input symbol, all possible nonencoded data sequences that satisfy the coding rule are estimated; then, several data sequences considered likely among the estimated data sequences are stored as paths, while the oldest symbol on the most likely of all the paths is obtained.
This decoding operation is described in detail in "Convolutional Codes and Their Performance in Communication Systems," IEEE TRANSACTIONS ON COMMUNICATIONS TECHNOLOGY, October 1971.
In the Viterbi decoding process, the likelihood of a path is represented by the path metric, the likelihood increasing with decreasing path metric. The path metric is obtained by summing the branch metrics, calculated for each symbol, along the branches.
More specifically, the Viterbi decoder performs ACS (add, compare, select) operations in which the branch metrics calculated at each point and the path metrics so far stored are added together in several combinations to obtain new path metric candidates, which are compared in several combinations so that the smaller one in each combination is selected and stored as the new path metric.
The circuit that performs the add, compare, and select operations is known as the add-compare-select circuit.
In the prior art, there is provided an add-compare-select circuit comprising: adding means for adding branch metrics and path metrics in prescribed combinations, thereby obtaining new path metric candidates; comparing means for comparing the thus obtained new path metrics; selecting means for selecting, on the basis of the comparison, the path metric candidate presented by the result of the addition in the adding means that corresponds to the simplified path metric judged as being the smallest; and storing means for storing the thus selected new path metric for use as a path metric at the next point in time.
This add-compare-select circuit is described in detail in "VLSI Architectures for Metric Normalization in the Viterbi Algorithm," IEEE CH2829-0/90, 1990.
In the prior art add-compare-select device having the above configuration, the operations of comparing the results of the additions and selecting an addition result based on the results of the comparisons are performed in a sequential manner within a given point in time.
However, addition and comparison operations generally involve a very long signal processing time; therefore, when the addition and comparison operations are performed in a sequential manner, the signal processing time becomes very long, limiting the rate of Viterbi decoding, etc. and making it imperative to reduce the data transmission rate.